package main

import "fmt"

type TreeNode2 struct {
	Left  *TreeNode2
	Right *TreeNode2
	Val   int
}

func deepestLeavesSum(root *TreeNode2) int {
	var queue []TreeNode2
	queue = append(queue, *root)
	sum := 0
	for len(queue) > 0 {
		sum = 0
		ql := len(queue)
		for i := 0; i < ql; i++ {
			v := queue[0]
			sum += v.Val
			queue = queue[1:]
			if nil != v.Left {
				queue = append(queue, *v.Left)
			}
			if nil != v.Right {
				queue = append(queue, *v.Right)
			}
		}
	}
	return sum
}

func main() {

	l5 := TreeNode2{
		Val: 5,
	}
	l7 := TreeNode2{
		Val: 7,
	}
	l4 := TreeNode2{
		Val:  4,
		Left: &l7,
	}
	l8 := TreeNode2{
		Val: 8,
	}
	l6 := TreeNode2{
		Val:   6,
		Right: &l8,
	}
	l3 := TreeNode2{
		Val:   3,
		Right: &l6,
	}
	l2 := TreeNode2{
		Val:   2,
		Left:  &l4,
		Right: &l5,
	}
	root := TreeNode2{
		Val:   1,
		Left:  &l2,
		Right: &l3,
	}

	fmt.Println(deepestLeavesSum(&root))
}
